package practice1_100;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Offer37 {
    //正序列化，利用层次遍历的思想
    public String serialize(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        StringBuffer strbu=new StringBuffer();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode temp=queue.poll();
            if(temp!=null){
                strbu.append(temp.val+",");
                queue.add(temp.left);
                queue.add(temp.right);
            }else{
                strbu.append("#,");
            }
        }
        return strbu.toString();
    }
    //反序列化，也可利用层次遍历的思想
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] temp=data.split(",");
        Queue<TreeNode> queue=new LinkedList<>();
        if(temp[0].equals("#"))return null;
        TreeNode root=new TreeNode(Integer.parseInt(temp[0]));
        queue.add(root);
        int index=1;
        while(!queue.isEmpty()){
            TreeNode tempnode=queue.poll();
            if(index<temp.length&&!temp[index].equals("#")&&tempnode!=null)
                tempnode.left=new TreeNode(Integer.parseInt(temp[index]));
            index++;
            if(index<temp.length&&!temp[index].equals("#")&&tempnode!=null)
                tempnode.right=new TreeNode(Integer.parseInt(temp[index]));
            index++;
            if(tempnode!=null&&tempnode.left!=null) queue.add(tempnode.left);
            if(tempnode!=null&&tempnode.right!=null)queue.add(tempnode.right);

        }
        return root;

    }

    public static void main(String[] args) {
        //[1,2,3,null,null,4,5,23,5]
//        TreeNode root=new TreeNode(1,new TreeNode(2),new TreeNode(3,new TreeNode(4,new TreeNode(23),new TreeNode(5)),new TreeNode(5)));
        TreeNode root=null;
        Offer37 demo=new Offer37();
        String a=demo.serialize(root);
        TreeNode res=demo.deserialize(a);
        System.out.println(res);
    }
    // Encodes a tree to a single string.
//    public String serialize(TreeNode root) {
//        List<Integer> list=new LinkedList<>();
//        if(root==null) return list.toString();
//
//        Queue<TreeNode> queue=new LinkedList<>();
//        queue.add(root);
//        while (!queue.isEmpty()){
//           TreeNode node= queue.poll();
//           if(root!=null) {
//               list.add(root.val);
//               queue.add(root.left);
//               queue.add(root.right);
//           }
//           else list.add(null);
//        }
//        //快慢指针
//        int fast=0,slow=0;
//        for (int i = 0; i < list.size(); i++) {
//            if(list.get(i)==null){
//                fast=i;
//            }else {
//               slow=fast=i;
//            }
//        }
//        return "";
//
//    }
//
//    // Decodes your encoded data to tree.
//    private TreeNode deserialize(String data) {
//        Queue<TreeNode> queue=new LinkedList<>();
//       String res= data.substring(data.indexOf("[")+1, data.lastIndexOf("]"));
//       String[] result= res.split(",");
//       TreeNode root=new TreeNode(Integer.parseInt(result[0]));
//       queue.add(root);
//       int index=1;
//       while (!queue.isEmpty()){
//           TreeNode treeNode= queue.poll();
//           if(index<= result.length-1){
//               TreeNode left=new TreeNode(Integer.parseInt(result[index++]));
//               treeNode.left=left;
//               queue.add(treeNode.left);
//           }
//           if(index+1<= result.length-1){
//               TreeNode right=new TreeNode(Integer.parseInt(result[index++]));
//
//           }
//       }
//        for (int i = 1; i < result.length/2; i=i++) {
//                if(!result[i].equals("null")){
//                    TreeNode left=new TreeNode(Integer.parseInt(result[i]));
//                    TreeNode right=new TreeNode(Integer.parseInt(result[i+1]));
//                }else {
//
//                }
//        }
//
//
//        return null;
//    }
//
//    public static void main(String[] args) {
//        System.out.println(new LinkedList<>().toString());
//        List<Integer> list=new LinkedList<>();
//
//        list.add(20);
//        list.add(null);
//        list.add(null);
//        list.add(20);        list.add(null);
//
//        System.out.println(list.toString());
//        new Offer37().deserialize("a");
//    }
}
